| Genetic algorithms are heuristic global optimization
methods that are based on the process of natural selection. Starting
from a randomly generated population of designs, the optimizer seeks to
produce improved designs from one generation to the next. This is
accomplished by exchanging genetic information between designs in the current
population in what is referred to as the crossover operation. Hopefully
this crossover produces improved designs that are then used to populate
the next generation.
I have been developing and using GA based optimization codes for several years now. My current code, PGA, is written for distributed memory parallel computers, such as those described here, uses the MPI libraries for all communications, and has an object-oriented code structure(C++). I've also combined my PGA code with a sequential quadratic programming (SQP) code for the enforcement of equality and inequality constraints. Micro-GAThe well-known problem of premature convergence for classical GA's can be avoided through the use of the micro-genetic algorithm method. The micro GA starts with a very small random population.The GA is used in the normal fashion on this small population until the binary strings of each individual differs from that of the best individual by less than some specified percentage. At this point the entire population, except for the best individual, is replaced by random designs. This periodic infusion of new genetic material allows the micro-GA to search the function space using a very small population. It will also keep the population from being dominated by designs corresponding to a local minimum found early in the optimization process. My PGA code can be used with Micro-GA technique or classic GA technique with various features such as niching and creep mutations. The code currently uses binary strings for variable encoding but I am currently writing a new code which can use real number encoding as well. Parallel GAGenetic algorithms are robust search techniques that are capable of avoiding local minima. However, for a complex function space with many local minima it may take many generations before the global minimum is located. This translates into hundreds and possibly thousands of function evaluations. If the function evaluation is expensive, such as a finite element analysis, it many take days or weeks to complete an optimization with a GA on a single workstation. However, one of the main advantages in using GA's is the fact that they are inherently parallel algorithms. Little effort is needed to modify an existing GA to make use of a parallel computer.The simplest way to parallelize a GA, and the method used in my code, is to use the synchronous master-slave model. Basically, the master processor does all computations relating to the actual GA, such as selection and crossover operations. The slave processors are tasked by the master to complete a function analysis of a given design and return the computed fitness. This model works well if all function analyses require the same amount of computation effort and have a long processing time relative to the amount of communication time needed to exchange information between master and slave. Simple ExampleAn optimization of a 2D analytic function was used to verify the accuracy of the micro-GA. This test function is given is show below:
This test function is difficult for a traditional gradient based optimizer since it has many false minima and would require an initial guess very close to the global minimum. This problem is also difficult for classic GA's (without niching or fitness sharing) due to the high amplitude of the "noise" in the function space and the lack of a strong global trend towards the global minimum. My micro GA based code was used with a population of 5, uniform crossover,
a 50% probability of crossover, tournament selection, and no mutation.
Both design variables were encoded with 9-bit strings and were limited
to the range -5 to 5.
ApplicationsMyself and other members of my research group have used my PGA code for several optimization projects. Some details can be found here. |
